'''
@author: Kevin Zhao
@date: Jan 7,2013
@note: Exercise 10.2-1
'''
class SinglyNode:
    next = None
    value = None
    def __init__(self, value):
        self.value = value
class SinglyLinkedList:
    head = None
    tail = None
    count = 0
    '''
    Insert the element onto the front of the list
    '''
    def insert(self,x):
        node = SinglyNode(x)
        if self.count == 0:
            self.head = node
            self.tail = node
        self.tail.next = node    
        self.tail = node
        self.count+=1
        return node
    def delete(self,x):
        temp = pre_temp = self.head
        while temp!=None:
            if temp.value == x:
                self.count-=1
                if temp == self.head:
                    self.head = temp.next
                    value = temp.value
                    pre_temp.next = None
                    temp = None
                    return value
                if temp == self.tail:
                    self.tail = pre_temp
                    value = temp.value
                    pre_temp.next = None
                    temp = None
                    return value
                pre_temp.next = temp.next
                value = temp.value
                pre_temp.next = None
                temp = None
                return value
            pre_temp = temp
            temp = temp.next
    def deleteByIndex(self,index):
        temp = pre_temp = self.head
        for i in range(0,index):
            pre_temp = temp
            temp = temp.next
        self.count-=1
        if temp == self.head:
            self.head = temp.next
            value = temp.value
            pre_temp.next = None
            temp = None
            return value
        if temp == self.tail:                
            self.tail = pre_temp
            value = temp.value
            pre_temp.next = None
            temp = None
            return value
        pre_temp.next = temp.next
        value = temp.value
        pre_temp.next = None
        temp = None
        return value
        
        
    def search(self,x):
        return
    
class DoublyLinkedList:
    def insert(self,x):
        return
    def delete(self,x):
        return
    def search(self,x):
        return